﻿#define _CRT_SECURE_NO_WARNINGS 1
// 动态规划

//class Solution {
//public:
//    int tribonacci(int n)
//    {
//        int a = 0, b = 1, c = 1;
//        int count = 3;
//        int result = 2;
//        if (n == 0)
//        {
//            return 0;
//        }
//        else if (n == 1 || n == 2)
//        {
//            return 1;
//        }
//        else
//        {
//            while (count != n)
//            {
//                a = b;
//                b = c;
//                c = result;
//                result = a + b + c;
//                count++;
//            }
//        }
//        return result;
//    }
//};

//class Solution {
//public:
//    int waysToStep(int n) {
//        vector<long long> dp(n + 1);
//        if (n == 1)
//        {
//            return 1;
//        }
//        if (n == 2)
//        {
//            return 2;
//        }
//        dp[0] = 1, dp[1] = 1, dp[2] = 2;
//        for (int i = 3; i <= n; i++)
//        {
//            dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % 1000000007;
//        }
//        return dp[n];
//    }
//};

//class Solution {
//public:
//    int minCostClimbingStairs(vector<int>& cost) {
//        if (cost.size() == 2) return min(cost[0], cost[1]);
//        for (int i = 2; i < cost.size(); i++)
//        {
//            cost[i] += min(cost[i - 1], cost[i - 2]);
//        }
//        return min(cost[cost.size() - 1], cost[cost.size() - 2]);
//    }
//};

//class Solution {
//public:
//    int numDecodings(string s) {
//        int len = s.size();
//        vector<int> dp(len);
//        if (s[0] != '0') dp[0] = 1;
//
//        if (len > 1 && s[1] == '0' && s[0] >= '1' && s[0] <= '2') dp[1] = 1;
//        if (len > 1 && s[0] != '0' && s[1] != '0')
//        {
//            int x = (s[0] - 48) * 10 + s[1] - 48;
//            if (x <= 26) dp[1] = 2;
//            else dp[1] = 1;
//        }
//
//        for (int i = 2; i < len; i++)
//        {
//            if (s[i] != '0') dp[i] += dp[i - 1];
//            int x = (s[i - 1] - 48) * 10 + s[i] - 48;
//            if (x >= 10 && x <= 26) dp[i] += dp[i - 2];
//        }
//        return dp[len - 1];
//    }
//};

//class Solution {
//public:
//    int uniquePaths(int m, int n) {
//        vector<vector<int>> dp(m);
//        for (int i = 0; i < m; i++)
//        {
//            dp[i].resize(n, 1);
//        }
//
//        for (int i = 1; i < m; i++)
//        {
//            for (int j = 1; j < n; j++)
//            {
//                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
//            }
//        }
//        return dp[m - 1][n - 1];
//    }
//};

//class Solution {
//public:
//    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
//        int m = obstacleGrid.size();
//        int n = obstacleGrid[0].size();
//        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
//        dp[0][1] = 1;
//
//        for (int i = 1; i <= m; i++)
//        {
//            for (int j = 1; j <= n; j++)
//            {
//                if (obstacleGrid[i - 1][j - 1] == 1)
//                {
//                    dp[i][j] = 0;
//                }
//                else
//                {
//                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
//                }
//
//            }
//        }
//        return dp[m][n];
//    }
//};

//class Solution {
//public:
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//     *
//     * @param grid int整型vector<vector<>>
//     * @return int整型
//     */
//    int maxValue(vector<vector<int> >& grid) {
//        int m = grid.size();
//        int n = grid[0].size();
//        for (int i = 1; i < m; i++)
//            grid[i][0] += grid[i - 1][0];
//        for (int j = 1; j < n; j++)
//            grid[0][j] += grid[0][j - 1];
//
//        for (int i = 1; i < m; i++)
//        {
//            for (int j = 1; j < n; j++)
//            {
//                grid[i][j] += max(grid[i - 1][j], grid[i][j - 1]);
//            }
//        }
//        return grid[m - 1][n - 1];
//    }
//};

//class Solution {
//public:
//    int MinData(int& x, int& y, int& z)
//    {
//        int data = min(x, y);
//        data = min(data, z);
//        return data;
//    }
//    int minFallingPathSum(vector<vector<int>>& matrix) {
//        int m = matrix.size();
//        int minpath = 0;
//        vector<vector<int>> dp(m + 2, vector<int>(m + 2));
//        // 初始化
//        for (int i = 0; i < m + 2; i++) dp[0][i] = 1000000;
//        for (int i = 0; i < m + 2; i++) dp[i][0] = dp[i][m + 1] = 1000000;
//        for (int i = 1; i <= m; i++) dp[1][i] = matrix[0][i - 1];
//
//        for (int i = 2; i <= m; i++)
//        {
//            for (int j = 1; j <= m; j++)
//            {
//                dp[i][j] = matrix[i - 1][j - 1] + MinData(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1]);
//            }
//        }
//        minpath = dp[m][1];
//        for (int j = 1; j <= m; j++)
//        {
//            minpath = min(minpath, dp[m][j]);
//        }
//        return minpath;
//    }
//};

//class Solution {
//public:
//    int minPathSum(vector<vector<int>>& grid) {
//        int m = grid.size();
//        int n = grid[0].size();
//
//        for (int i = 1; i < n; i++) grid[0][i] += grid[0][i - 1];
//        for (int i = 1; i < m; i++) grid[i][0] += grid[i - 1][0];
//
//        for (int i = 1; i < m; i++)
//        {
//            for (int j = 1; j < n; j++)
//            {
//                grid[i][j] += min(grid[i][j - 1], grid[i - 1][j]);
//            }
//        }
//
//        return grid[m - 1][n - 1];
//    }
//};
 